
joint.routers.ice = (function(g, _, joint) {

  'use strict';

  var config = {

    // size of the step to find a route
    step: 8,

    // use of the perpendicular linkView option to connect center of element with first vertex
    perpendicular: true,

    // should be source or target not to be consider as an obstacle
    excludeEnds: [], // 'source', 'target'

    // should be any element with a certain type not to be consider as an obstacle
    excludeTypes: ['ice.Info'],

    // if number of route finding loops exceed the maximum, stops searching and returns
    // fallback route
    maximumLoops: 2000,

    // possible starting directions from an element
    startDirections: ['right', 'bottom'],

    // possible ending directions to an element
    endDirections: ['left', 'top'],

    // specify directions above
    directionMap: {
      right: { x: 1, y: 0 },
      bottom: { x: 0, y: 1 },
      left: { x: -1, y: 0 },
      top: { x: 0, y: -1 }
    },

    // maximum change of the direction
    maxAllowedDirectionChange: 90,

    // padding applied on the element bounding boxes
    paddingBox: function() {

      var step = 2;

      return {
        x: -step,
        y: -step,
        width: 2 * step,
        height: 2 * step
      };
    },

    // an array of directions to find next points on the route
    directions: function() {

      var step = this.step;

      return [
        { offsetX: step  , offsetY: 0     , cost: step },
        { offsetX: 0     , offsetY: step  , cost: step },
        { offsetX: -step , offsetY: 0     , cost: step },
        { offsetX: 0     , offsetY: -step , cost: step }
      ];
    },

    // a penalty received for direction change
    penalties: function() {

      return {
        0: 0,
        45: this.step / 2,
        90: this.step / 2
      };
    },

    // * Deprecated *
    // a simple route used in situations, when main routing method fails
    // (exceed loops, inaccessible).
    /* i.e.
      function(from, to, opts) {
        // Find an orthogonal route ignoring obstacles.
        var point = ((opts.previousDirAngle || 0) % 180 === 0)
                ? g.point(from.x, to.y)
                : g.point(to.x, from.y);
        return [point, to];
      },
    */
    fallbackRoute: _.constant(null),

    // if a function is provided, it's used to route the link while dragging an end
    // i.e. function(from, to, opts) { return []; }
    draggingRoute: null
  };

  // Map of obstacles
  // Helper structure to identify whether a point lies in an obstacle.
  function ObstacleMap(opt, paper) {

    this.map = {};
    this.options = opt;
    this.paper = paper;
    // tells how to divide the paper when creating the elements map
    this.mapGridSize = 100;
  }

  ObstacleMap.prototype.build = function(graph, link) {

    var opt = this.options;

    // source or target element could be excluded from set of obstacles
    var excludedEnds = _.chain(opt.excludeEnds)
        .map(link.get, link)
        .pluck('id')
        .map(graph.getCell, graph).value();

    // Exclude any embedded elements from the source and the target element.
    var excludedAncestors = [];

    var source = graph.getCell(link.get('source').id);
    if (source) {
      excludedAncestors = _.union(excludedAncestors, _.map(source.getAncestors(), 'id'));
    }

    var target = graph.getCell(link.get('target').id);
    if (target) {
      excludedAncestors = _.union(excludedAncestors, _.map(target.getAncestors(), 'id'));
    }

    // builds a map of all elements for quicker obstacle queries (i.e. is a point contained
    // in any obstacle?) (a simplified grid search)
    // The paper is divided to smaller cells, where each of them holds an information which
    // elements belong to it. When we query whether a point is in an obstacle we don't need
    // to go through all obstacles, we check only those in a particular cell.
    var mapGridSize = this.mapGridSize;

    // Compute rectangles from all the blocks
    var blockRectangles =_.chain(graph.getElements())
    // remove source and target element if required
    .difference(excludedEnds)
    // remove all elements whose type is listed in excludedTypes array
    .reject(function(element) {
      // reject any element which is an ancestor of either source or target
      return _.contains(opt.excludeTypes, element.get('type')) || _.contains(excludedAncestors, element.id);
    })
    // change elements (models) to their bounding boxes
    .invoke('getBBox').value();

    // Compute rectangles from all the port labels
    var state = this.paper.options.getState();
    var labelRectangles = $('.port-label').map(function(index, node) {
      var rect = V(node).bbox();
      return g.rect({
        x: (rect.x - state.pan.x) / state.zoom,
        y: (rect.y - state.pan.y) / state.zoom,
        width: rect.width / state.zoom,
        height: rect.height / state.zoom
      });
    }).toArray();

    // Add all rectangles to the map's grid
    _.chain(blockRectangles.concat(labelRectangles))
    // expand their boxes by specific padding
    .invoke('moveAndExpand', opt.paddingBox)
    // build the map
    .foldl(function(map, bbox) {

      var origin = bbox.origin().snapToGrid(mapGridSize);
      var corner = bbox.corner().snapToGrid(mapGridSize);

      for (var x = origin.x; x <= corner.x; x += mapGridSize) {
        for (var y = origin.y; y <= corner.y; y += mapGridSize) {

          var gridKey = x + '@' + y;

          map[gridKey] = map[gridKey] || [];
          map[gridKey].push(bbox);
        }
      }

      return map;

      }, this.map).value();

    return this;
  };

  ObstacleMap.prototype.isPointAccessible = function(point) {

    var mapKey = point.clone().snapToGrid(this.mapGridSize).toString();

    return _.every(this.map[mapKey], function(obstacle) {
      return !obstacle.containsPoint(point);
    });
  };

  // Sorted Set
  // Set of items sorted by given value.
  function SortedSet() {
    this.items = [];
    this.hash = {};
    this.values = {};
    this.OPEN = 1;
    this.CLOSE = 2;
  }

  SortedSet.prototype.add = function(item, value) {

    if (this.hash[item]) {
      // item removal
      this.items.splice(this.items.indexOf(item), 1);
    } else {
      this.hash[item] = this.OPEN;
    }

    this.values[item] = value;

    var index = _.sortedIndex(this.items, item, function(i) {
      return this.values[i];
    }, this);

    this.items.splice(index, 0, item);
  };

  SortedSet.prototype.remove = function(item) {
    this.hash[item] = this.CLOSE;
  };

  SortedSet.prototype.isOpen = function(item) {
    return this.hash[item] === this.OPEN;
  };

  SortedSet.prototype.isClose = function(item) {
    return this.hash[item] === this.CLOSE;
  };

  SortedSet.prototype.isEmpty = function() {
    return this.items.length === 0;
  };

  SortedSet.prototype.pop = function() {
    var item =  this.items.shift();
    this.remove(item);
    return item;
  };

  function normalizePoint(point) {
    return g.point(
      point.x === 0 ? 0 : Math.abs(point.x) / point.x,
      point.y === 0 ? 0 : Math.abs(point.y) / point.y
    );
  }

  // reconstructs a route by concating points with their parents
  function reconstructRoute(parents, point, startCenter, endCenter) {

    var route = [];
    var prevDiff = normalizePoint(endCenter.difference(point));
    var current = point;
    var parent;

    while ((parent = parents[current])) {

      var diff = normalizePoint(current.difference(parent));

      if (!diff.equals(prevDiff)) {
        route.unshift(current);
        prevDiff = diff;
      }

      current = parent;
    }

    var startDiff = normalizePoint(g.point(current).difference(startCenter));
    if (!startDiff.equals(prevDiff)) {
      route.unshift(current);
    }

    return route;
  }

  // find points around the rectangle taking given directions in the account
  function getRectPoints(bbox, directionList, opt) {

    var step = opt.step;
    var center = bbox.center();
    var startPoints = _.chain(opt.directionMap).pick(directionList).map(function(direction) {

      var x = direction.x * bbox.width / 2;
      var y = direction.y * bbox.height / 2;

      var point = center.clone().offset(x, y);

      if (bbox.containsPoint(point)) {
        point.offset(direction.x * step, direction.y * step);
      }

      return point.snapToGrid(step);

    }).value();

    return startPoints;
  }

  // returns a direction index from start point to end point
  function getDirectionAngle(start, end, dirLen) {

    var q = 360 / dirLen;
    return Math.floor(g.normalizeAngle(start.theta(end) + q / 2) / q) * q;
  }

  function getDirectionChange(angle1, angle2) {

    var dirChange = Math.abs(angle1 - angle2);
    return dirChange > 180 ? 360 - dirChange : dirChange;
  }

  // heurestic method to determine the distance between two points
  function estimateCost(from, endPoints) {

    var min = Infinity;

    for (var i = 0, len = endPoints.length; i < len; i++) {
      var cost = from.manhattanDistance(endPoints[i]);
      if (cost < min) {
        min = cost;
      }
    }

    return min;
  }

  // finds the route between to points/rectangles implementing A* alghoritm
  function findRoute(start, end, map, opt) {

    var step = opt.step;
    var startPoints, endPoints;
    var startCenter, endCenter;

    // set of points we start pathfinding from
    if (start instanceof g.rect) {
      startPoints = getRectPoints(start, opt.startDirections, opt);
      startCenter = start.center().snapToGrid(step);
    } else {
      startCenter = start.clone().snapToGrid(step);
      startPoints = [startCenter];
    }

    // set of points we want the pathfinding to finish at
    if (end instanceof g.rect) {
      endPoints = getRectPoints(end, opt.endDirections, opt);
      endCenter = end.center().snapToGrid(step);
    } else {
      endCenter = end.clone().snapToGrid(step);
      endPoints = [endCenter];
    }

    // take into account only accessible end points
    startPoints = _.filter(startPoints, map.isPointAccessible, map);
    endPoints = _.filter(endPoints, map.isPointAccessible, map);

    // Check if there is a accessible end point.
    // We would have to use a fallback route otherwise.
    if (startPoints.length > 0 && endPoints.length >  0) {

      // The set of tentative points to be evaluated, initially containing the start points.
      var openSet = new SortedSet();
      // Keeps reference to a point that is immediate predecessor of given element.
      var parents = {};
      // Cost from start to a point along best known path.
      var costs = {};

      _.each(startPoints, function(point) {
        var key = point.toString();
        openSet.add(key, estimateCost(point, endPoints));
        costs[key] = 0;
      });

      // directions
      var dir, dirChange;
      var dirs = opt.directions;
      var dirLen = dirs.length;
      var loopsRemain = opt.maximumLoops;
      var endPointsKeys = _.invoke(endPoints, 'toString');

      var currentDirAngle;
      var previousDirAngle;

      // main route finding loop
      while (!openSet.isEmpty() && loopsRemain > 0) {

        // remove current from the open list
        var currentKey = openSet.pop();
        var currentPoint = g.point(currentKey);
        var currentDist = costs[currentKey];
        previousDirAngle = currentDirAngle;
        /* jshint -W116 */
        currentDirAngle = parents[currentKey] ? getDirectionAngle(parents[currentKey], currentPoint, dirLen)
            : opt.previousDirAngle != null ? opt.previousDirAngle : getDirectionAngle(startCenter, currentPoint, dirLen);
        /* jshint +W116 */

        // Check if we reached any endpoint
        if (endPointsKeys.indexOf(currentKey) >= 0) {
          // We don't want to allow route to enter the end point in opposite direction.
          dirChange = getDirectionChange(currentDirAngle, getDirectionAngle(currentPoint, endCenter, dirLen));
          if (currentPoint.equals(endCenter) || dirChange < 180) {
            opt.previousDirAngle = currentDirAngle;
            return reconstructRoute(parents, currentPoint, startCenter, endCenter);
          }
        }

        // Go over all possible directions and find neighbors.
        for (var i = 0; i < dirLen; i++) {

          dir = dirs[i];
          dirChange = getDirectionChange(currentDirAngle, dir.angle);
          // if the direction changed rapidly don't use this point
          // Note that check is relevant only for points with previousDirAngle i.e.
          // any direction is allowed for starting points
          if (previousDirAngle && dirChange > opt.maxAllowedDirectionChange) {
            continue;
          }

          var neighborPoint = currentPoint.clone().offset(dir.offsetX, dir.offsetY);
          var neighborKey = neighborPoint.toString();
          // Closed points from the openSet were already evaluated.
          if (openSet.isClose(neighborKey) || !map.isPointAccessible(neighborPoint)) {
            continue;
          }

          // The current direction is ok to proccess.
          var costFromStart = currentDist + dir.cost + opt.penalties[dirChange];

          if (!openSet.isOpen(neighborKey) || costFromStart < costs[neighborKey]) {
            // neighbor point has not been processed yet or the cost of the path
            // from start is lesser than previously calcluated.
            parents[neighborKey] = currentPoint;
            costs[neighborKey] = costFromStart;
            openSet.add(neighborKey, costFromStart + estimateCost(neighborPoint, endPoints));
          }
        }

        loopsRemain--;
      }
    }

    // no route found ('to' point wasn't either accessible or finding route took
    // way to much calculations)
    return opt.fallbackRoute(startCenter, endCenter, opt);
  }

  // resolve some of the options
  function resolveOptions(opt) {

    opt.directions = _.result(opt, 'directions');
    opt.penalties = _.result(opt, 'penalties');
    opt.paddingBox = _.result(opt, 'paddingBox');

    _.each(opt.directions, function(direction) {

      var point1 = g.point(0, 0);
      var point2 = g.point(direction.offsetX, direction.offsetY);

      direction.angle = g.normalizeAngle(point1.theta(point2));
    });
  }

  // initiation of the route finding
  function router(vertices, opt) {

    resolveOptions(opt);

    /* jshint -W040 */

    // enable/disable linkView perpendicular option
    this.options.perpendicular = !!opt.perpendicular;

    // Force source/target BBoxes to be points

    this.sourceBBox.x += this.sourceBBox.width / 2;
    this.sourceBBox.y += this.sourceBBox.height / 2;
    this.sourceBBox.width = 0;
    this.sourceBBox.height = 0;

    this.targetBBox.x += this.targetBBox.width / 2;
    this.targetBBox.y += this.targetBBox.height / 2;
    this.targetBBox.width = 0;
    this.targetBBox.height = 0;

    // expand boxes by specific padding
    var sourceBBox = g.rect(this.sourceBBox);
    var targetBBox = g.rect(this.targetBBox);

    // pathfinding
    var map = (new ObstacleMap(opt, this.paper)).build(this.paper.model, this.model);
    var oldVertices = _.map(vertices, g.point);
    var newVertices = [];
    var tailPoint = sourceBBox.center().snapToGrid(opt.step);

    var from;
    var to;

    // find a route by concating all partial routes (routes need to go through the vertices)
    // startElement -> vertex[1] -> ... -> vertex[n] -> endElement
    for (var i = 0, len = oldVertices.length; i <= len; i++) {

      var partialRoute = null;

      from = to || sourceBBox;
      to = oldVertices[i];

      if (!to) {

        to = targetBBox;

        // 'to' is not a vertex. If the target is a point (i.e. it's not an element), we
        // might use dragging route instead of main routing method if that is enabled.
        var endingAtPoint = !this.model.get('source').id || !this.model.get('target').id;

        if (endingAtPoint && _.isFunction(opt.draggingRoute)) {
          // Make sure we passing points only (not rects).
          var dragFrom = from instanceof g.rect ? from.center() : from;
          partialRoute = opt.draggingRoute(dragFrom, to.origin(), opt);
        }
      }

      // if partial route has not been calculated yet use the main routing method to find one
      partialRoute = partialRoute || findRoute(from, to, map, opt);

      if (partialRoute === null) {
        // The partial route could not be found.
        // use orthogonal (do not avoid elements) route instead.
        if (!_.isFunction(joint.routers.orthogonal)) {
          throw new Error('Manhattan requires the orthogonal router.');
        }
        return joint.routers.orthogonal(vertices, opt, this);
      }

      var leadPoint = _.first(partialRoute);

      if (leadPoint && leadPoint.equals(tailPoint)) {
        // remove the first point if the previous partial route had the same point as last
        partialRoute.shift();
      }

      tailPoint = _.last(partialRoute) || tailPoint;

      Array.prototype.push.apply(newVertices, partialRoute);
    }

    /* jshint +W040 */

    return newVertices;
  }

  // public function
  return function(vertices, opt, linkView) {

    if (linkView.sourceMagnet) {
      opt.startDirections = [linkView.sourceMagnet.attributes.pos.value];
    }

    if (linkView.targetMagnet) {
      opt.endDirections = [linkView.targetMagnet.attributes.pos.value];
    }

    return router.call(linkView, vertices, _.extend({}, config, opt));
  };

})(g, _, joint);
